package com.practice.shua1;

import java.util.LinkedList;

/**
 * 【leetcode 239】（TODO：滑动窗口+窗口内最大值的更新结构）
 * 【题目】：
 * 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
 * 【示例1】：
 * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 * 输出：[3,3,5,5,6,7]
 * 解释：
 * 滑动窗口的位置                   最大值
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       3
 *  1 [3  -1  -3] 5  3  6  7       3
 *  1  3 [-1  -3  5] 3  6  7       5
 *  1  3  -1 [-3  5  3] 6  7       5
 *  1  3  -1  -3 [5  3  6] 7       6
 *  1  3  -1  -3  5 [3  6  7]      7
 *【示例2】：
 * 输入：nums = [1], k = 1
 * 输出：[1]
 * 【示例3】：
 * 输入：nums = [1,-1], k = 1
 * 输出：[1,-1]
 * 【示例4】：
 * 输入：nums = [9,11], k = 2
 * 输出：[11]
 * 【示例5】：
 * 输入：nums = [4,-2], k = 2
 * 输出：[4]
 * 【提示】：
 * 1 <= nums.length <= 10^5
 * -10^4 <= nums[i] <= 10^4
 * 1 <= k <= nums.length
 *
 * @author lineng
 * @create 2021-05-02 19:55
 */
public class Code_04_SlidingWindowMaxArray {

    // TODO：当前面过程提交超时
    // 需要优化
    public static int[] maxSlidingWindow3(int[] nums, int k) {

        if (nums == null || k < 1 || nums.length < k) {
            return null;
        }

        // 单调双端队列（队列中放数组中的index）
        // index代表的值
        // 头 ----> 尾
        // 大 ----> 小
        // R++时，从尾部进，从尾部出，先进队列在R++
        // L++时，达到条件时，从头部出，先L++在判断是否出队列
        LinkedList<Integer> indexQueue = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            rMoveRightUpdateQueue(nums, i, indexQueue);
        }
        LinkedList<Integer> resMid = new LinkedList<>();
        if (!indexQueue.isEmpty()){
            Integer curFirstIndex = indexQueue.peekFirst();
            resMid.add(nums[curFirstIndex]);
        }
        int left = -1;
        for (int right = k-1; right < nums.length-1; right++) {
            // 下面会让right+1，因此条件为right < nums.length-1

            left = right-k+1;
            rMoveRightUpdateQueue(nums, right+1, indexQueue);
            lMoreRightUpdateQueue(nums, left+1, indexQueue);
            if (!indexQueue.isEmpty()){
                Integer curFirstIndex = indexQueue.peekFirst();
                resMid.add(nums[curFirstIndex]);
            }
        }
        int[] resultArr = new int[resMid.size()];
        for (int i = 0; i < resMid.size(); i++) {
            resultArr[i] = resMid.get(i);
        }

        return resultArr;
    }

    // right位置相进队列
    public static void rMoveRightUpdateQueue(int [] nums, int right, LinkedList<Integer> queue){
        if (queue.isEmpty()){
            queue.addLast(right);
            return;
        }
        // 当前right位置的数
        int curNum = nums[right];
        // 当前队尾位置的数
        int lastIndex = queue.peekLast();
        int lastNum = nums[lastIndex];
        while (curNum >= lastNum && !queue.isEmpty()){
            // 一直弹出不合格的队尾
            queue.pollLast();
            if (!queue.isEmpty()){
                lastIndex = queue.peekLast();
                lastNum = nums[lastIndex];
            }
        }
        // 加入right
        queue.addLast(right);
    }

    // l来到了left位置后，判断队头位置是否合格
    public static void lMoreRightUpdateQueue(int [] nums, int left, LinkedList<Integer> queue){
        if (queue.isEmpty()){
            return;
        }
        int firstIndex = queue.peekFirst();
        if (firstIndex < left){
            queue.pollFirst();
        }
    }

    // 自己优化下 AC 通过
    public static int[] maxSlidingWindow(int[] nums, int k) {

        if (nums == null || k < 1 || nums.length < k) {
            return null;
        }

        // 单调双端队列（队列中放数组中的index）
        // index代表的值
        // 头 ----> 尾
        // 大 ----> 小
        // R++时，从尾部进，从尾部出，先进队列在R++
        // L++时，达到条件时，从头部出，先L++在判断是否出队列
        int[] resArr = new int[nums.length-k+1];
        LinkedList<Integer> indexQueue = new LinkedList<>();
        int resIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i<k-1){
                rMoveRightUpdateQueue(nums, i, indexQueue);
                continue;
            }
            if (i == k-1){
                rMoveRightUpdateQueue(nums, i, indexQueue);
                if (!indexQueue.isEmpty()){
                    Integer curFirstIndex = indexQueue.peekFirst();
                    resArr[resIndex++] = nums[curFirstIndex];
                }
                continue;
            }
            rMoveRightUpdateQueue(nums, i, indexQueue);
            lMoreRightUpdateQueue(nums, i-k+1, indexQueue);
            if (!indexQueue.isEmpty()){
                Integer curFirstIndex = indexQueue.peekFirst();
                resArr[resIndex++] = nums[curFirstIndex];
            }
        }
        return resArr;
    }





















    // AC 通过
    public static int[] maxSlidingWindow2(int[] arr, int w) {

        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        // 其中放的是位置，头代表 （大->小）尾
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        // L...R
        //     i
        for (int R = 0; R < arr.length; R++) { // 当前让 i -> [i] 进窗口 ， i 就是 r
            // R -> 值  可以放在比他大的数后，或者空
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
                qmax.pollLast();
            }
            qmax.addLast(R);
            // 数进来了
            // 如果窗口没有形成W的长度之前，不弹出数字的
            if (qmax.peekFirst() == R - w) {
                qmax.pollFirst();
            }
            // 以上窗口更新做完了
            if (R >= w - 1) {
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    // for test
    public static void printArr(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }


    public static void main(String[] args) {
        int[] arr = {1,3,-1,-3,5,3,6,7};
        int w = 3;
        int[] ints = maxSlidingWindow3(arr, w);
        printArr(ints);
        System.out.println("====");
        int[] ints1 = maxSlidingWindow(arr, w);
        printArr(ints1);
    }

}
